四种最短路算法的总结：Dijkstra,堆优化Dijkstra,bellman |
您所在的位置：网站首页 › bellman ford算法复杂度 › 四种最短路算法的总结：Dijkstra,堆优化Dijkstra,bellman |
|
第一个最短路算法：Dijstra Dijstra原题链接 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。 输入格式 第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 yy 的有向边，边长为 zz。 输出格式 输出一个整数，表示 1号点到 n 号点的最短距离。 如果路径不存在，则输出 −1。 数据范围 1≤n≤n≤500, 1≤m≤10^5, 图中涉及边长均不超过10000。 输入样例： 3 3 1 2 2 2 3 1 1 3 4此处我们约定整张图构成的集合为V，已经确定了最短路径的集合为S，初始时，S只有源点 朴素的dijkstra算法用贪心思想，有点类似于最小生成树中的prim算法，将整张图分为已经确定了最小路径的点所组成的集合S与V-S，每次都遍历S与V-S的路径，如果V-S中的某个节点到S集合的路径dist[j]要小于其到源点的距离，则进行松弛操作dist[j]=dist[t]+w[t][j];并将其并入集合S中 代码： #include #include #include using namespace std; const int N=510; int g[N][N],dist[N],n,m; //判断某点是否位于集合S中 bool state[N]; int Dijstra(){ memset(dist,0x3f,sizeof dist); dist[1]=0; //对于n个节点进行迭代 for(int i=0;im; while(m--){ int a,b,c; cin>>a>>b>>c; //重边取最小值 g[a][b]=min(g[a][b],c); } cout>n>>m; memset(h,-1,sizeof h); while(m--){ int x,y,z; cin>>x>>y>>z; add(x,y,z); } cout3 1 * 如果没有备份数组，则从1到3的最短距离确实是2 * 但如果限制了边数，那么k=1时候，最短距离应该是3 * 正确做法是用上轮节点2更新的距离--无穷大，来更新节点3， 再取最小值，所以节点3离起点的距离是3。 */ memcpy(backup,dist,sizeof dist); for(int j=0;j>n>>m>>k; for(int i=0;i>a>>b>>c; e[i]={a,b,c}; } bellman_ford(); //由于图中存在负权值，导致就算到不了n节点，其距离也有可能减小，故取得无穷大的一一半就能认为到达不了 if(dist[n]>0x3f3f3f3f/2) cout>m; memset(h,-1,sizeof h); while(m--){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } spfa(); if(dist[n]==0x3f3f3f3f) cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |